package com.julius.design.suanfa.search;

/**
 * @author julius
 * @date 2021-10-25 上午 10:38
 * <p>
 *      旋转数组中的最小值
 *      https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 * </p>
 */
public class MinArrayOne {

    /**
     * 旋转数组的的最小值查找
     * [3,4,5,5,5,6,7,8,1,2,3]
     *  0 1 2 3 4 5 6 7 8 9 10
     *  旋转数组如果发生了旋转，最小值肯定小于等于第一个数，如果中间的数大于第一个数，那么肯定在右边
     * @param numbers
     * @return
     */
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];
    }
}
